package leetcode_900;

import java.util.Stack;

/**
 *@author 周杨
 *ScoreOfParentheses_856_ 算括号的值 AB=A+B (A)=2*A 
 *describe:用栈 非常经典的题目 要注意同等等级的数值入栈和出栈 AC 74%
 *2018年11月4日 下午5:04:07
 */
public class ScoreOfParentheses_856_ {
	public int scoreOfParentheses(String S) {
        Stack<Integer> stack=new Stack<Integer>();
        stack.push(0);
        for(char c:S.toCharArray()) {
        	if(c=='(')
        		stack.push(0);//左括号全是0
        	else {
        		int before=stack.pop();//当前匹配到的括号值
        		int far=stack.pop();//同级别的括号值
        		stack.push(far+Math.max(1, 2*before));
        	}
        }
        return stack.pop();
    }
}
